// https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> left(n, 0), right(n, 0);

        int maxHeight = 0;
        for (int i = 0; i < n; i++) {
            if (height[i] > maxHeight) {
                maxHeight = height[i];
            }
            left[i] = maxHeight;
        }

        maxHeight = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (height[i] > maxHeight) {
                maxHeight = height[i];
            }
            right[i] = maxHeight;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += min(left[i], right[i]) - height[i];
        }
        return ans;
    }
};